/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int getSize(struct Node *root) {
    if (root == NULL) return 0;
    int sum = 1;
    for (int i = 0; i < root->numChildren; i++) {
        sum += getSize(root->children[i]);
    }
    return sum;
}

void __preorder(struct Node *root, int *k, int *ret) {
    if (root == NULL) return ;
    ret[*k] = root->val;
    *k += 1;
    for (int i = 0; i < root->numChildren; i++) {
        __preorder(root->children[i], k, ret);
    }
    return;
}

int* preorder(struct Node* root, int* returnSize) {
    int n = getSize(root);
    int *ret = (int *)malloc(sizeof(int) * n);
    int k = 0;
    __preorder(root, &k, ret);
    *returnSize = n;
    return ret; 
}
